import { ListNode, arrToList, listToArr } from '../../utils/listUtil.js';
/**15. 三数之和
 * - 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足ijk互不相等 ，同时还满足 三数和 == 0
 * - 返回所有和为 0 且不重复的三元组
 */
export function threeSum(nums: number[] = [-1, 0, 1, 2, -1, -4]): number[][] {
    // 关键点： 排序、三指针、三指针都要去重

    // 定一找2，双指针： i从左往右遍历，在遍历过程中用双指针。其中left是i+1， right是length-1
    // 先给数组排好序，三数之和为0，那么肯定是有正有负的，所以这种三个指针正负都能照顾到。
    // 在i的for循环中，给left和right来一个while循环，如果三数之和不为目标值，就适当的移动left或right指针。
    //[ -4, -1, -1, 0, 1, 2 ]
    //       i      L  R      ---> 三指针的指向示例   
    const res: number[][] = []
    nums.sort((a, b) => a - b)
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) return res  //数组排序了，如果最左边的指针已经大于0了，是不可能凑成0的

        let left = i + 1
        let right = nums.length - 1

        // 去重1，如果当前的数字与之前的一样，就跳过 ，因为题目要求不能有重复的三元组
        if (nums[i] === nums[i - 1]) continue //去重

        while (left < right) {
            const threeNum = nums[i] + nums[left] + nums[right]
            if (threeNum > 0) {
                right--
            } else if (threeNum < 0) {
                left++
            } else {
                res.push([nums[i], nums[left], nums[right]])
                //去重2：两指针都要去重
                while (left < right && nums[left] === nums[left + 1]) left++
                while (left < right && nums[right] === nums[right - 1]) right--
                //找到答案，双指针收缩
                left++
                right--
            }
        }

    }
    return res
}
/**16. 最接近的三数之和
 * - 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 * - 返回这三个数的和。假定每组输入只存在恰好一个解。
 */
export function threeSumClosest(nums: number[] = [-1, 2, 1, -4], target: number = 1): number {
    //思路与上一题一样 
    nums.sort((a, b) => a - b)
    let res = Infinity
    for (let i = 0; i < nums.length; i++) {
        /**当前元素 */
        const element = nums[i];
        /**左指针 */
        let left = i + 1
        /**右指针 */
        let right = nums.length - 1

        while (left < right) {
            /**本次while中的三数之和 */
            const threesum = element + nums[left] + nums[right]
            if (Math.abs(threesum - target) < Math.abs(res - target)) res = threesum //绝对值最小的作为res

            if (threesum < target) {//小于target，说明left指针需要右移动，才能碰到更大的元素
                left++
            } else if (threesum > target) {//大于target，说明right需要向左移动，才能碰到更小的元素
                right--
            } else {//三数之和为target，则直接return了
                return res
            }
        }

    }

    return res
}
/**18. 四数之和
 * - 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]  
 * - a、b、c 和 d 互不相同， 四数和为target
 */
export function fourSum(nums: number[] = [2, 2, 2, 2, 2], target: number = 8): number[][] {
    //三数之和就是 一个for循环+left right指针 O(n^2)  （暴力解法是 n3）
    //四数之和就是 两个for循环+left right指针 O(n^3)  （暴力解法是 n4）
    //n数之和 用双指针法。 i为第一个数 j (i+1)为第二个数 left (j+1)第三个数,right(length-1)最后一个数
    //然后找不到正确结果的时候，不断缩小left 和 right （大于target就right--，小于就left++）
    //找到正确结果之后，需要看看接下来可能在left和right缩小范围时，和nums[left]、nums[right]相同的数，有就去重
    //在前面两层for遍历的时候，也需要分别对i和j去重
    //四数之和就比三数之和多一层循环，定二找二. 这一题把i和j定下来，然后left和right移动
    nums.sort((a, b) => a - b) //排序了！！
    const res: [number, number, number, number][] = []
    for (let i = 0; i < nums.length; i++) {
        const numI = nums[i];
        if (nums[i - 1] === numI) continue //去重1
        for (let j = i + 1; j < nums.length; j++) {//j是i+1
            const numJ = nums[j];
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;//去重2. 注意这里j有范围限制，避免第一次就跳过了
            let left = j + 1
            let right = nums.length - 1

            while (left < right) {
                const four = numI + numJ + nums[left] + nums[right]
                if (four < target) {//比目标小，说明left需要右移才能找到更大的
                    left++
                } else if (four > target) {//比目标大，说明right需要左移找更小的
                    right--
                } else {
                    res.push([numI, numJ, nums[left], nums[right]])
                    //去重3
                    while (left < right && nums[left] === nums[left + 1]) left++
                    while (left < right && nums[right] === nums[right - 1]) right--
                    left++
                    right--
                }
            }
        }
    }
    return res
}
/**19. 删除链表的倒数第 N 个结点
 * - 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 */
export function removeNthFromEnd(head: ListNode | null = arrToList([1, 2, 3, 4, 5]), n: number = 2): ListNode | null {
    //双指针巧解：如果要删除倒数第n个，那么就设置俩指针，让fast先走n步，然后再两个一起走，fast到底之后，slow刚好就是要删除的位置
    /**虚拟头结点 */
    const _head = new ListNode(0, head)
    let fast: ListNode | null = _head, slow: ListNode | null = _head
    while (n-- && fast) {//fast指针先走n步
        fast = fast.next
    }
    fast = fast!.next//由于删除链表的特殊性，需要让fast多走一步，slow才能是被删除的节点的前驱
    while (fast) {//直到fast走到末尾
        fast = fast.next
        slow = slow!.next
    }
    slow!.next = slow!.next!.next //删除

    return _head.next
}
/**27. 移除元素
 * - 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 * - 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
 * - 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 */
export function removeElement(nums: number[], val: number): number {
    //头尾指针：改变元素顺序
    let left: number = 0, right: number = nums.length - 1
    while (left <= right) {
        while (left <= right && nums[left] !== val) {//找到左边等于val的元素
            left++
        }
        while (left <= right && nums[right] === val) {//找到右边不等于val的元素
            right--
        }
        if (left < right) {
            nums[left++] = nums[right--] //把右边的不等于val的 ，覆盖到左边val身上，实现“删除”
        }
    }
    return left
}
/**31. 下一个排列
 * - 给你一个整数数组 nums ，找出 nums 的下一个排列。
 * - “下一个”指的是按字典顺序升序的下一个。比如 123的下一个是132
 */
export function nextPermutation(nums: number[] = [3, 2, 1]): void {
    /* 1234的按顺序的全排列：供找规律
        1 2 3 4
        1 2 4 3
        1 3 2 4
        1 3 4 2
        1 4 2 3
        1 4 3 2
        2 1 3 4
        2 1 4 3
        2 3 1 4
        2 3 4 1
        2 4 1 3
        2 4 3 1
        3 1 2 4
        3 1 4 2
        3 2 1 4
        3 2 4 1
        3 4 1 2
        3 4 2 1
        4 1 2 3
        4 1 3 2
        4 2 1 3
        4 2 3 1
        4 3 1 2
        4 3 2 1
    */
    //思路：找当前数组的下一个全排列 （按字典顺序从小到大， 比如 213 的下一个是 231、123的下一个是132）
    //实际上就是从后往前找，一旦遇到了 某个字符 比 它身后的某个字符 要小的话，就交换位置，然后i+1的部分反转 （其实就是排序） （可以看上面给出的1234全排列，找规律）
    //如果遍历结束后还没发现，那说明当前数组字典序最大的了（比如321），下一个数组就是字典序最小的（123），直接反转就行

    /**反转数组函数，可以指定开始和结束位置 */
    const reverse = (arr: any[], start: number = 0, end: number = arr.length - 1): void => {
        while (start <= end) {
            [arr[start], arr[end]] = [arr[end], arr[start]] //使用es6快速交换两个值
            start++
            end--
        }
    }

    //从后往前遍历，找 “ 某个字符 比 它身后的某个字符 要小 ”
    for (let i = nums.length - 1; i >= 0; i--) {
        for (let j = nums.length - 1; j > i; j--) {//注意，j必须小于i，
            if (nums[j] > nums[i]) {
                [nums[j], nums[i]] = [nums[i], nums[j]] //交换这俩
                //然后反转i+1后部分 （其实就是排序）
                reverse(nums, i + 1)
                return
            }
        }
    }
    //最后还没return，说明当前是字典末尾了，需要找字典开头的
    reverse(nums) //直接反转即可

    console.log(nums);


}
/**82. 删除排序链表中的重复元素 II
 * - 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
 * - eg: 输入：head = [1,2,3,3,4,4,5]
 * - 输出：[1,2,5]
 */
export function deleteDuplicates(head: ListNode | null = arrToList([1, 2, 3, 3, 4, 4, 5])): ListNode | null {
    //思路：双指针。用一个指针来记录“上一个不重复的节点”，比如[1, 2, 3, 3, 4, 4, 5]中的1 2 5。
    // 遍历链表，如果发现下一个和当前不相同，就可以让 lastNode 往后推进一位
    // 如果发现下一个是相同的，就让指针一直往后，直到指针的数值和 lastNode 不相同为止
    const dummyHead = new ListNode(0, head)
    /**上一个节点(已经确定不重复的节点) */
    let lastNode = dummyHead;
    while (head && head.next) {
        if (head.val != head.next.val) {
            // 当前节点已经确认不重复，将lastNode向后移动一位 
            // 注意head始终是等于last.next的,因此当head不重复时，我们操作lastNode即可
            lastNode = lastNode.next!;
        } else {
            // 遍历找到与当前节点不重复的点
            while (head.next && head.val == head.next.val) head = head.next;
            // 将 lastNode 的下一个节点赋值为不重复的节点
            lastNode.next = head.next;
        }
        // 将当前节点后移一位
        head = lastNode.next
    }
    return dummyHead.next
}
/**283. 移动零
 * - 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 
 */
export function moveZeroes(nums: number[]) {
    //快慢指针 - 双遍历、慢指针填充0
    let slow = 0
    for (let fast = 0; fast < nums.length; fast++) {//这一次遍历就可以把0全部删掉了
        if (nums[fast] !== 0) {
            nums[slow] = nums[fast]
            slow++
        }
    }
    for (; slow < nums.length; slow++) {//然后把slow后面的全部变为0
        nums[slow] = 0
    }

    // //快慢指针：单遍历、交换 
    // let slow = 0 
    // for (let fast = 0; fast < nums.length; fast++) {//这一次遍历就可以把0全部删掉了
    //     if (nums[fast] !== 0) {
    //         //交换位置，把0往后挪
    //         const temp = nums[slow]
    //         nums[slow] = nums[fast]
    //         nums[fast] = temp
    //         slow++
    //     }
    // }
}
/**647. 回文子串的个数
 * - 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目 
 * - 还有动规解法
 */
export function countSubstrings(s: string = "abc"): number {

    //双指针法：从左往右遍历，判断以xxx为中心点，有几个回文串

    /**判断这个字符串的回文个数（从中心往两边扩散计算） 
     * - 首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。
     * - 在遍历中心点的时候，要注意中心点有两种情况：一个元素可以作为中心点，两个元素也可以作为中心点（奇数和偶数） 
     * @param str 字符串
     * @param i 中心位置1（往左扩散）
     * @param j 中心位置2（往右扩散）
     */
    const huiwen = (str: string, i: number, j: number) => {
        let res = 0
        while (i >= 0 && j < s.length && s[i] === s[j]) {  //如果当前是相同的，那么回文个数+1
            res++
            i--
            j++
        }
        return res
    }
    //计算最终结果：
    let res = 0
    for (let i = 0; i < s.length; i++) {
        const element = s[i];
        res += huiwen(s, i, i)// 以i为中心
        res += huiwen(s, i, i + 1)// 以i和i+1为中心
    }
    return res
}
/**977. 有序数组的平方
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 */
export function sortedSquares(nums: number[]): number[] {
    let left = 0
    let right = nums.length - 1
    const res: number[] = []
    let k = nums.length - 1  //用来给res从后往前索引
    while (left <= right) {
        const leftCount = nums[left] * nums[left]
        const rightCount = nums[right] * nums[right]
        console.log(leftCount, rightCount);

        if (leftCount >= rightCount) {
            res[k--] = leftCount
            left++
        } else {
            res[k--] = rightCount
            right--
        }
    }
    return res
}